package com.zx.练习题._2020面试题;

/**
 * 【快手】最短编辑距离
 * UNIX系统下有一个行编辑器ed，它每次只对一行文本做删除一个字符、插入一个字符或替换一个字符三种操作。
 * 例如某一行的内容是“ABC”，经过把第二个字符替换成“D”、删除第一个字符、末尾插入一个字符“B”，这三步操作后，内容就变成了“DCB”。
 * 即“ABC”变成“DCB”需要经过3步操作，我们称它们的编辑距离为3。
 * 现在给你两个任意字符串（不包含空格），请帮忙计算它们的最短编辑距离。
 * 输入描述
 * 输入包含多组数据。
 *
 * 每组数据包含两个字符串m和n，它们仅包含字母，并且长度不超过1024。
 * 输出描述
 * 对应每组输入，输出最短编辑距离。
 * 示例1
 * 输入
 * ABC CBCD
 * ABC DCB
 * 输出
 * 2
 * 3
 *
 * https://leetcode.cn/problems/edit-distance/
 */
public class 最短编辑距离 {

    public static void main(String[] args) {
        System.out.println(new 最短编辑距离().minDistance("ABC", "DCB"));
        System.out.println(new 最短编辑距离().minDistance("horse", "ros"));
    }

    public int minDistance(String word1, String word2) {
        boolean eq = word1.length() == word2.length();

        int count = 0;
        if (eq) {
            //相等就替换
            for (int i = 0; i < word1.length(); i++) {
                if (word1.charAt(i) != word2.charAt(i)) {
                    count++;
                }
            }
            return count;
        }

        // 不等就添加+替换
        // 1、找到相似的节点，可能不用全部替换。就两个字符串的交集
        int a1_begin = -1;
        int a1_end = -1;
        String findStr = null;
        for (int i = 0; i < word1.length(); i++) {
            for (int j = word1.length(); j >= i && (a1_end - a1_begin < j - i); j--) {
                String str = word1.substring(i, j);
                int f = word2.indexOf(str);
                //找到了
                if (f >= 0) {
                    a1_begin = i;
                    a1_end = j;
                    findStr = str;
                }
            }
        }

        System.out.println("发现集合" + findStr);
        count = Math.abs(word2.length() - word1.length())//需要插入的数据量
                + (word2.length() - (a1_end - a1_begin)); //需要替换的数据量
        System.out.println("最短路径" + count);

        return count;
    }
}
